

function say() {
    alert("LC:703. 数据流中的第 K 大元素");
}
say();


/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    //3:30-45
    this.heap = new MinHeap()
    this.cap = k

    for(var i = 0; i < nums.length; i++){
        this.add(nums[i])
    }
};

/**
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.heap.insert(val)
    if(this.heap.size() > this.cap){
        this.heap.removeTop()
    }else {

    }
    return this.heap.top()
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * var obj = new KthLargest(k, nums)
 * var param_1 = obj.add(val)
 */


class MinHeap {
    constructor(){
        this.arr = [null]
    }

    heapify(index){
        var arr = this.arr
        var count = this.arr.length

        while(true){
            var minIdx = index
            if(index * 2 < count && arr[index * 2] < arr[index]){
                minIdx = index * 2
            }
            if(index * 2 + 1 < count && arr[index * 2 + 1] < arr[minIdx]){
                minIdx = index * 2 + 1
            }
            if(minIdx == index){
                break
            }
            this.swap(arr, minIdx, index)
            index = minIdx
        }
    }

    swap(arr, i, j){
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }

    size(){
        return this.arr.length - 1
    }

    top(){
        return this.arr[1]
    }

    removeTop(){
        this.arr.splice(1,1) //???
        this.heapify(1)
    }

    insert(val){
        this.arr.push(val)
        for(var i = this.arr.length - 1; i > 0; i--){ //???从后往前堆化,从前往后不行?
            this.heapify(i)
        }
    }
}
